import java.util.*;

/**
 * 692. 前K个高频单词
 * https://leetcode.cn/problems/top-k-frequent-words/description/
 */
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for(String s : words) {
            map.put(s, map.getOrDefault(s, 0) + 1);
        }

        PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>(
                (a, b) -> {
                    if(a.getValue() == b.getValue()) {
                        // 频次相同，使用大根堆
                        return b.getKey().compareTo(a.getKey());
                    } else {
                        // 频次不相同，使用小根堆
                        return a.getValue() - b.getValue();
                    }
                });
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            heap.offer(entry);
            if(heap.size() > k) {
                heap.poll();
            }
        }

        List<String> ret = new LinkedList<>();
        while(!heap.isEmpty()) {
            Map.Entry<String, Integer> tmp = heap.poll();
            ret.add(tmp.getKey());
        }

        // 逆序链表
        Collections.reverse(ret);

        return ret;
    }
}